The present invention relates to a wire length minimization apparatus and method of performing total wire length minimization considering priority, which is performed next to area minimization processing in one-dimensional compaction of layout data of a semiconductor integrated circuit.
This application is based on Japanese Patent Application No. 9-201518, filed Jul. 28, 1997 and Japanese Patent Application No. 9-347851, filed Dec. 17, 1997, the content of which is incorporated herein by reference.
In designing a semiconductor integrated circuit represented by an IC, constituent elements (to be referred to as "objects" herein) such as semiconductor objects and wires are laid out in a limited area. To make a compact semiconductor integrated circuit and reduce the manufacturing cost in such design, it is important to minimize the layout area.
Processing of automatically minimizing the layout area by reducing the object interval is called compaction. The tool used for compaction is called a compactor. Note that an object means a group of layouts for simultaneous movement in the same certain direction by the same distance (or the layouts locally have a fixed relative positional relationship) in compaction.
In designing a large-scale IC layout, when the layout is roughly designed by a designer and then optimized using a compactor, the load on the designer can be reduced. When an advance in the manufacturing technique allows to change the design rule and reduce the initial object interval, the layout area can be automatically reduced by using the compactor. The compactor is used in various situations.
The wire length minimization problem to be described later is an important problem in this compaction processing.
From the viewpoint of a decrease in labor, the compactor is important in optimizing the large-scale layout. It is difficult to quickly and strictly optimize the two-dimensional wiring on the large-scale layout. However, although strict optimization is hardly done, it suffices that a compact layout capable of standing practical use can be quickly generated, and in many cases, compaction processing is sequentially performed in each direction (one-dimensional compaction).
FIG. 1 shows the arrangement of a conventional compactor for performing one-dimensional compaction. The horizontal direction of an IC layout will be referred to as the x direction, and the vertical direction as the y direction hereinafter for the descriptive convenience.
First, layout data is input from an input section 202.
A compaction direction setting section 204 sets the compaction direction to one of the X and y directions. Assume that compaction is performed in the x direction for the first and third times and in the y direction for the second and fourth times.
A constraint graph creating section 206 creates a constraint graph expressing the positional constraint relationship of objects for each compaction direction. The objects are made to correspond to the vertices (nodes) of the constraint graph, and the limit proximity distance between two objects corresponding to two vertices connected by a branch is stored in the constraint graph. After this, processing is performed with reference to this constraint graph.
An area minimization section 208 moves the objects to one side along the compaction direction as close as possible with reference to the constraint graph. For example, in compaction in the x direction, the objects are moved to the left side as close as possible. Assume that the area minimization section 208 moves the objects in a direction for decreasing the x-coordinate values of the vertices.
A wire length minimization section 210 moves the objects to minimize the wire length with reference to the constraint graph. The objects have already been moved in the direction for minimizing the x-coordinate values of the vertices by the area minimization section 208, so the objects cannot be moved anymore in the direction of decreasing the x-coordinate values of the vertices. Therefore, the wire length minimization section 210 performs only processing of increasing the x-coordinate values of the vertices.
A completion determining section 212 determines whether the completion condition is satisfied. If the completion condition is satisfied, processing is ended, and the result is output from an output section 214. If the completion condition is not satisfied, processing is transferred back to the compaction direction setting section 204, and the compaction processing is repeatedly performed while changing the compaction direction.
Processing in the area minimization section 208 and that in the wire length minimization section 210 will be described below. As described above, the area minimization section 208 moves the objects to one side along the compaction direction. As a result, when processing in the area minimization section 208 is complete, the wire length partially increases. Such an increase in wire length upon processing in the area minimization section 208 will be described with reference to FIGS. 2A to 2C.
To reduce a layout having four objects A to D as shown in FIG. 2A in the x direction, the area minimization section 208 moves the objects to the left side. As a result, the object C is moved to the left side, as shown in FIG. 2B. In FIG. 2C, the object C is close to the right, as compared to FIG. 2B, though the entire layout area does not change. That is, the object C need not always be fully moved to the left to minimize the area. Additionally, the layout in FIG. 2B is inferior to that in FIG. 2C in the following two points.
(1) The wire in FIG. 2B is too long, and the resistance is higher than that of the given layout.
(2) In FIG. 2B, in the next compaction in the y direction, the object A cannot be moved to the lower side because of the object C. For this reason, the finally output layout area becomes large.
Generally, in moving the objects to one side as close as possible to minimize the area, the area does not change in a certain range even when the objects are moved. As can be seen from comparison between FIG. 2B and FIG. 2C, minimization of the wire length often contributes to minimization of the entire area (e.g., reference 1"Y. E. Cho: A Subjective Review of Compaction, Proc. 22nd Design Automation Conference, 1985, pp. 396-404"). Therefore, the problem to be solved by processing of the wire length minimization section 210 is how to minimize the wire length within this allowable range.
This problem is called a wire length minimization problem, and it is an important problem in one-dimensional compaction.
More generally speaking, the wire length minimization problem can be defined as "a problem for minimizing the cost under the constraint condition". To realize more effective one-dimensional compaction, it is important to efficiently solve this problem. The wire length minimization problem will be described below.
The "cost" will be described first. Although processing in the x direction will be described below, this also applies to processing in the y direction.
In minimizing the total wire length, the whole length cannot be sufficiently shortened only by shortening the individual wires. In addition, if the wires have different priorities for minimization, these priorities cannot be taken into consideration. Therefore, a cost based on all wires is defined, and the individual objects are moved to reduce the cost.
Line segments of a straight wire and a polygonal wire will be referred to as lines. The wire length in the x direction can be obtained by calculating the sum of the lines in the x direction.
The wires have different priorities for minimization. For example, generally, a wire belonging to a mask layer with a high resistance is required to be preferentially shortened. In this case, the line length is multiplied by a predetermined priority to calculate the cost. Letting x.sub.i be the x-coordinate value of each inflection of a wire, and c.sub.ij be the priority, the cost is given by equation (1). Assume that a line having a large level of priority must be preferentially shortened. In this case, J is a set of combinations of suffixes corresponding to two ends of lines. EQU cost =.SIGMA.c.sub.ij .vertline.x.sub.i -x.sub.j .vertline.(1)
(i, j).di-elect cons.J PA1 i
Elimination of the absolute value symbols of equation (1) and rearrangement of the result of elimination yields equation (2): EQU cost =.SIGMA.w.sub.i x.sub.j (2)
Equations (1) and (2) are equivalent within the range where the magnitude relationship between the x-coordinate values of the two ends of the line does not reverse.
In equation (2), the cost can be reduced by decreasing the x-coordinate value x.sub.i when a coefficient w.sub.i is a positive value or by increasing the x-coordinate value x.sub.i when the coefficient w.sub.i is a negative value. Since equations (1) and (2) must be equivalent, this operation must be performed without replacing the left and right of the line with each other. To minimize equation (1), the left and right of the line must be replaced with each other. However, once the left and right of a line are replaced with each other, equation (2) must be corrected.
When the line having a length of 0 is inverted at an appropriate timing to rewrite the cost of equation (2), the cost of equation (1) can be minimized.
The above-described "constraint condition" will be described next.
Assume that x.sub.i represents the x-coordinate value of a side of a polygon representing an object including the inflection of a wire, unless otherwise specified. The design rule is a condition defined by the manufacturing process and also a constraint condition associated with the positional relationship between objects. This condition can be generally represented as follows. EQU x.sub.i -x.sub.j .gtoreq.d.sub.ij (3)
This x-coordinate value x.sub.i and a vertex of the constraint graph are made to correspond to each other, thereby expressing equation (3) as a constraint graph shown in FIG. 3.
In the constraint graph, the coordinate value X(v) is stored in a vertex v, and a constraint condition value D(e) is stored in a branch e. The branch in FIG. 3 represents EQU X(v.sub.q)-X(v.sub.p).gtoreq.D(e.sub.pq) (4)
Generally, the coordinate value x.sub.i of the end point of line and the coordinate value X(v.sub.p) of a vertex corresponding to the end point hold a relation x.sub.i =X(v.sub.p)+c.sub.i (c.sub.i is a constant) therebetween. Therefore, by eliminating the constant term, the cost is given by: ##EQU1##
FIG. 4 shows an example of a general constraint graph. Since a sink corresponding to the right end point of the layout and a source corresponding to the left end point are added, the constraint graph is a connected graph.
The wire length minimization problem is a problem for minimizing the cost of equation (1) within a range where the constraint condition represented by the constraint graph is satisfied.
A local improvement method and a group improvement method as conventional wire length minimization methods will be described below.
To reduce the cost, when a weight W(v.sub.p) of a vertex v.sub.p is positive, the vertex position is decreased, and when the weight of the vertex is negative, the vertex position is increased. Before one-dimensional minimization processing, area minimization processing is performed to make the coordinate values of each vertex as small as possible. Therefore, the wire length minimization section cannot further decrease the coordinate value of each vertex. For this reason, as described above, the wire length minimization section only need to perform processing of increasing the coordinate values of each vertex.
When the weight of each vertex is negative, the cost can be considerably reduced by increasing the coordinate values of each vertex within the range not violating the constraint condition. This method is called the local improvement method.
However, only with the local improvement method, the cost converges to a solution far from the optimum solution, as is known. In an example shown in FIG. 5, the wire lengths cannot be sufficiently minimized by the local improvement method. Bullets near the wires mean that objects on both sides cannot come close to each other anymore.
In the example of FIG. 5, however, when a plurality of objects are simultaneously moved, an arrangement with a lower cost can be obtained. Consider the group of objects A to H in FIG. 5. A wire length with priority 4 is connected to this object group from the right side while a wire with priority 1 and a wire with priority 2 are connected to this object group from the left side. When all the objects are simultaneously moved to the right side, the wire with priority 1 and the wire with priority 2 extend. However, the wire with priority 4 is shortened, and the cost is reduced. Even when the three hatched objects B, D, and E are simultaneously moved, the cost can be reduced.
The method of simultaneously moving a plurality of vertexes in one group is called the group improvement method. Whether the cost can be reduced by moving the entire group to the right side can be determined by calculating the sum of weights of all vertexes in the group. As in the local improvement method, when the sum value is negative, the cost can be reduced by moving the group to the right side.
In the group improvement method, processing can be efficiently executed by storing, in a tree, vertexes to be simultaneously moved in a group. The tree has branches of a tight constraint graph, which direct from parents to children. The group of vertexes to be simultaneously moved changes over time during processing. Therefore, every time the group is moved, the members of the tree must be corrected.
In FIG. 5, the cost can be sufficiently reduced by moving not all objects but the three hatched objects B, D, and E to the right. In this state, the optimum operation is movement of the three objects B, D, and E. The problem is how to efficiently obtain a tree having the three objects B, D, and E as members.
In a conventional method (e.g., reference 2 "W. L. Schiele: Improved Compaction by Minimized Length of Wires, Proc. 20th Design Automation Conf., 1983, pp. 121-127", reference 3 "G. Lakhani, R, Varadarajan: A Wire-Length Minimization Algorithm for Circuit Layout Compaction, IEEE International Symposium on Circuits and Systems, Vol. 1, pp. 276 -279", or reference 4 "C. Kingsley: A Hierarchical, Error-Tolerant Compactor, IEEE 21st Design Automation Conf., 1984, pp. 126-132"), the sum of weights of vertexes on routes from the root of the tree to the vertexes is obtained as an accumulated value. If the accumulated value of a certain leaf is positive, the vertexes on this route are fixed, and the remaining vertexes are separated and moved. This method will be described with reference to FIGS. 6A and 6B.
In FIG. 6A, a numerical value in a circle representing a vertex is the wight of the vertex, and a numerical value in parentheses near each vertex represents the accumulated value of the weights on the route. A weight is the desired degree of movement of the vertex to the left, and a vertex having a negative accumulated value is a candidate to be moved to the right. A vertex without the negative accumulated value is not moved. According to the conventional method, vertexes v.sub.301 to v.sub.303 on the lowest route must be fixed. These vertexes are separated, as shown in FIG. 6B. Next, in the remaining partial trees, vertexes having a negative sum value are searched for. As a result, two vertexes v.sub.304 and v.sub.305 enclosed by a broken line in FIG. 6B are moved to the right side.
In the layout shown in FIG. 5, however, the three hatched objects B, D, and E cannot be satisfactorily moved by employing this method.
FIG. 7 shows a tree in which accumulated values are calculated for groups corresponding to FIG. 5. As is apparent from FIG. 7, since all the leaves have negative accumulated values, this tree cannot be decomposed to separate the objects B, D, and E. That is, a tree having, as members, the three hatched objects B, D, and E in the layout shown in FIG. 5 cannot be obtained by the conventional group improvement method.
In addition to the above-described methods, methods of executing linear programming scheme on a graph to obtain an optimum solution (reference 5"J. Lee, C. K. Wong: A Performance-Aimed Cell Compactor with Automatic Jogs, IEEE Trans. Computer-Aided Design, Vol. 11, No. 12, 1992, pp. 1495-1507, 1992", and reference 6 "T. Yoshimura: A Graph Theoretical Compaction Algorithm, IEEE Proc. ISCA 85, 1985,pp. 1455-1458") have also been proposed. However, in these methods, the processing speed is low.
As described above, in the conventional one-dimensional compaction processing, when the group improvement method is used in wire length minimization processing next to area minimization processing, object movement for cost reduction of the wires is allowed. However, the objects which can be moved cannot be specified, so that such objects cannot be moved and the sufficient compaction cannot be performed. When linear programming scheme is used for wire length minimization processing, the processing requires a long time.